package my.senix.classics;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;

/**
 * 将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
 * <p>
 * Created by lhs on 2018/11/7.
 */
public class DecompositionPrime {

    /**
     * f(n)表示分解n的质因数，那 f(n)=2*f(n/2),
     * 故用递归。
     * 2的64次方是个大数，最多也就64次递归
     */

    public static void main(String[] args) {

        List<Integer> childPrimes = new LinkedList<>();

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {

            String str;
            while (true) {
                str = reader.readLine();

                if (str == null || str.equalsIgnoreCase("-1")) {
                    break;
                }

                Integer num = Integer.valueOf(str);

                f(num, childPrimes);

                System.out.print(num + "=");
                for (int i = 0; i < childPrimes.size(); i++) {
                    if (i == 0) {
                        System.out.print(childPrimes.get(i));
                    } else {
                        System.out.print("*" + childPrimes.get(i));
                    }
                }
                System.out.println();

                childPrimes.clear();
            }


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static void f(Integer num, List<Integer> childPrimes) {
        boolean find=false;
        for (int i = 2; i < Math.sqrt(num); i++) {
            if (num % i == 0) {
                find=true;
                childPrimes.add(i);
                f(num/i,childPrimes);
                break;
            }
        }
        if(!find){
            childPrimes.add(num);
        }

    }

}
